iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 6
2

正規語言概論
這門大概是純數學的課之中
跟機率並列兩門我最喜歡的數學課
Introduction to the Theory of Computation (2nd Edition), Michael Sipser, Thomson Course Technology
image

一開始又是複習集合等概念(後面不會再出現啦)
然後重點開始
開始定義 Finite state machine 以及他能計算的regular set & regular expression
接著帶出 FSM 不能算的東西
於是把FSM加上一個stack memory之後 發明了 pushdown automata
讓他可以計算的種類延伸到context-free grammar
然後又帶出了pushdown automata沒辦法算的東西
所以不用stack的memory
而是變成一個可以random access的memory之後
就產生的Turing machine
這也就是電腦的數學理論模型了
發明者Alan Turing也被稱為電腦科學之父
Turing在密碼學跟人工智慧貢獻也很大
可以去看看 模仿遊戲 這部電影喔

之後基於 Turing machine 之上
我們可以來探討怎樣的問題是不能解的(比如說電腦能不能自己寫出一個程式來)
或是計算的效率 P & NP 問題

我認為Turing machine產生的是 imperative programming 的程式設計模式
另一個跟Turing machine等價的數學模型是lamda calculation
這算是functional programming的理論吧
但後者我就不是很清楚了

雖然很理論
但是finite state machine的模型以及regular expression都是很強大的工具
context-free grammar也是很重要的

其實我覺得系上把這門課從必修拿掉有點可惜...

密碼學
戲稱ㄇㄇ學
算是數學課喔
D.R. Stinson, "Cryptography: theory and practice", 3rd Ed, CRC Press, 2005
image
從簡單的密碼分析 古典加密
HASH function(SHA)
兩大類加密法(encryption)

  1. 對稱式加密(或是 私鑰加密): DES AES
  2. 非對稱式加密(或是 公鑰加密): RSA

注意 hash跟encryption不一樣喔
hash是一個單向的function
output的結果是不可逆的
而且使用上相同的input是不會有collision的(雖然理論上會有)
但encryption是可逆的
只要有key output是可以轉回到input

所以hash function通常是用來產生辨別各個不同的物件的ID
而encryption function就是用來保護content
這講得很粗略就是

對稱跟非對稱主要就是差在你是一把還是兩把KEY
前者運算很快後者很慢
所以通常用後者來保護前者的KEY
非對稱加密也可以用在數位簽章上面
如果要加密就是
用公鑰來加密 接收者可以用它的私鑰解密
如果要做簽章驗證的話
就用私鑰來簽名 用公鑰來驗證

以上大概是最實用的部分XD

在來還介紹了
橢圓曲線密碼學
share secret (當大家想要確保沒有一個人可以獨享那份寶藏 所以把key分成多份給大家 一定要大家都到齊 才能解)
等等
其實這領域超大的
要踏入這領域的話 數學很重要喔

作業系統概論
Operating System Concepts, by Abraham Silberschatz, Greg Gagne, Peter Baer Galvin
這本書就著名的恐龍本
因為封面都是恐龍XD
image

OS就是在負責分配硬體資源
所以裡面很多的議題都是在講如何分配讓各種資源使用效益最大化
基本上是很理論的課(不過還是要看作業怎麼出就是)

那是鳩竟是那些資源要被分配呢?

  1. CPU
    多個process/thread怎麼去分配CPU的計算能力 (scheduling algorithm)
    也會讓你練習multi-process跟multi-thread的程式
    會提到concurrent programming所需要注意的事情
    像是race condition, synchronization, starvation, deadlock, lock等等議題
  2. Memory
    介紹memory management system, page, virtual memory (當記憶體不夠的時候)
  3. Hard disk
    介紹 storage and file system

不過曾聽一個大大說過
與其聽這些理論
不如直接去trace Linux source code
而我認識有trace過Linux source code的人
也都是大大沒錯
供大家參考大大們的學習方式

或是多去觀察各項參數等等

計算機組織概論
戲稱 祭祖
David A. Patterson and John L. Hennessy, Computer Organization & Design-- The Hardware/Software Interface, 4th edition, 2009
著名的白算盤書
基本上就是告訴你電腦怎麼運作的
image
image
電腦分成五個部分

  1. Input
    就像是鍵盤 滑鼠 麥克風的資訊輸入等等
  2. output
    就是你輸出的東西
  3. memory
    儲存資料跟instruction set的地方
  4. datapath
  5. control
    這兩個合在一起 就是所謂的CPU
    datapath負責運算執行指令的部分
    control就是控制資料流 指揮動作

再來就是跟你講怎麼設計解析指令集
然後就是要設計一個電路來解析指令集
共分成五個階段

  1. instruction fetch
  2. instruction decode
  3. execution
  4. memory access
  5. write back

可以一個指令佔據這五個階段
也可以採用pipeline的方式
當其他指令在某個階段的時候
其他指令就可以利用其他的階段
這就是pipeline的概念

雖然我後來不是做硬體設計的
但這概念也還是可以用在軟體設計上喔

作業基本上就是用verilog實作這樣的CPU出來
從single phase到pipleine這樣

但pipeline是我大學四年唯一沒有做出來的作業(倒地)

不過我是滿喜歡這門課的
整個理論架構的建立非常清楚
這本書真的寫得很好
即使不是走硬體的人也很直得去看看

編譯器設計概論
這門課也是很CS專門的課
我覺得也是一個滿重要的課
畢竟他是一個把理論工程化並且實作出來的一門課
到現在編譯器還是很重要的
C.N. Fischer, R.K. Cytron, and R.J. LeBlanc, Jr., Crafting a Compiler, Addison-Wesley, 2010.
我們用這本書
不是有名的屠龍書就是

image

基本上就是用 finite state machine
先去做lexical analysis分析出每個token
然後介紹各種parser的演算法來做 syntactic analysis
建立abstract syntax tree
之後就用這棵樹來產生object code
很可惜的是沒有講到optimzation的部分就是

我很喜歡這門課的專案
因為我們真的實作了一個compiler出來
給定一個小的語言
我們用lex做scanner
yacc做parser
最後我用這個產生出了assembler可以執行的 intel x86 assembly code
基本上就是整個compiler的過程
超有成就感的啦

人工智慧概論
Artificial Intelligence A Modern Approach (2nd Edition), Stuart Russell and Peter Norving, Second edition, Prentice Hall.
這本也是聖經本
涵蓋的範圍很完整
可以讓你很了解AI發展的脈絡
我覺得寫得還算不錯的一本課本
不過當時沒有好好的讀
有點可惜
後來論文有用到一部份
再回去看看 才發現真的是一本寶藏啊

image

第一部分可是希望電腦也能自己解決問題
基本上的概念就是暴力解去找出所有的可能
找到是答案的那一個
當然這樣很慢
所以有很多很多改進的方法
就誕生了許多新的演算法

當然一堆if也有它的極限
所以後來開始有了用邏輯推理的方式來建立的專家系統
有點像是你建立了一堆邏輯推論的句子到他的database去
今天碰到一個新的問題
他就可以利用邏輯推演來推理出答案
logical programming就是這樣來的

下一part講的是不確定情況的問題
這邊就會用到大量的機率模型了
馬可夫模型就是很有名的代表例子
還有像是決策理論等等
隨著邏輯推演的方法到了瓶頸
剛好計算能力 儲存容量 網路通訊進步
我們可以收集並且分析足比以前還大量的資料了
利用新的能力所以帶來的新的資料
模型的的深度也比以前還深
讓 機器學習 類神經網路 深度學習(滿滿的buzz word)
就成為AI領域的主要顯學了
這門課就暫時沒提到(哪時候沒有alpha go也還沒紅起來)

作業很有趣 也滿難的
用Python去做Pacman的演算法
http://ai.berkeley.edu/project_overview.html
(可惜也是我當年沒有好好做的一個專案 嗚嗚)
有興趣可以去看看

計算機網路管理
Network Administration (NA)
就是教你網管相關的知識
也是系上的招牌操課
可以參考以下課綱
https://people.cs.nctu.edu.tw/~liuyh/course/netadm/content.php
會先教Perl來做script
然後複習基本的TCP/IP
然後就是
NAT, DHCP, FTP, Firewall, Mail system(Postfix), DNS, News, SNMP等各式各樣的應用服務
很操
但也是對架設系統的訓練就是

網路安全
William Stallings, Cryptography and Network Security, Principles and Practices, Prentice Hall, 2003
image
大概就是介紹TCP/IP各層的安全
印象中也包含一些邏輯上的推導去證明是安全的
不過雖然這門課是研究所課程
但其實講的都很基本就是了...

反正網路安全基本上記得三大點CIA

  1. C (Confidentiality) 保密性
    你傳輸的東西不能給不該看得人看到
    解法就是加密囉
    所以一大部分的問題就在怎樣交換key這個議題
  2. I(Integrity) 完整性
    你傳輸的東西 不能被竄改
    解法利用hash function產生特徵值 讓接收者去比對
  3. A(Availability) 可用性
    就是你的服務是要是可用的 而不會連不上
    像是DDOS可能就會癱瘓你的服務了
    防禦方法大概就是防火牆吧

RFID資訊系統
image
這也是研究所的課
介紹RFID這技術到相關的protocol
到相關的應用以及商務系統等

遍佈式計算
Pervasive Computing
一個很大很廣的概念
就是任何東西都可以運算
所以像是冰箱 電視 眼鏡等等等
那時候智慧型手機還沒出來
手機出來之後 手機跟平板就變成一個很重要的終端設備就是
也可以說這是現在智慧家庭 智慧城市 IOT的前身吧XD
這領域包含得很廣
前面 跟user互動的介面設計 偵測收集資訊的sensor等嵌入式系統
中間的通訊系統 行動網路
一直到後面處理大量資料的server/middleware 雲端運算
都是探討的課題之一
反正累積了滿滿的buzz words
就變成滿滿做project的好題材
這門課最後就變成有點像創業競賽提案就是

最近稍微有點熱起來的邊緣運算也算呢~

微算機系統實驗
介紹8051的軟硬體
但我真的不記得在做什麼了.......
天阿.......


上一篇
爆肝風城:資工大二課程
下一篇
啊我到底在幹嘛 : 資工大四課程
系列文
不前不後,不上不下,一個曾經交大資工書卷的軟體工程師成長之路30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言